/*
 * Copyright (c) 1997, 2013, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.lang;

import java.lang.ref.*;
import java.util.Objects;
import java.util.concurrent.atomic.AtomicInteger;
import java.util.function.Supplier;

/**
 * This class provides thread-local variables.  These variables differ from
 * their normal counterparts in that each thread that accesses one (via its
 * {@code get} or {@code set} method) has its own, independently initialized
 * copy of the variable.  {@code ThreadLocal} instances are typically private
 * static fields in classes that wish to associate state with a thread (e.g.,
 * a user ID or Transaction ID).
 *
 * <p>For example, the class below generates unique identifiers local to each
 * thread.
 * A thread's id is assigned the first time it invokes {@code ThreadId.get()}
 * and remains unchanged on subsequent calls.
 * <pre>
 * import java.util.concurrent.atomic.AtomicInteger;
 *
 * public class ThreadId {
 *     // Atomic integer containing the next thread ID to be assigned
 *     private static final AtomicInteger nextId = new AtomicInteger(0);
 *
 *     // Thread local variable containing each thread's ID
 *     private static final ThreadLocal&lt;Integer&gt; threadId =
 *         new ThreadLocal&lt;Integer&gt;() {
 *             &#64;Override protected Integer initialValue() {
 *                 return nextId.getAndIncrement();
 *         }
 *     };
 *
 *     // Returns the current thread's unique ID, assigning it if necessary
 *     public static int get() {
 *         return threadId.get();
 *     }
 * }
 * </pre>
 * <p>Each thread holds an implicit reference to its copy of a thread-local
 * variable as long as the thread is alive and the {@code ThreadLocal}
 * instance is accessible; after a thread goes away, all of its copies of
 * thread-local instances are subject to garbage collection (unless other
 * references to these copies exist).
 *
 * @author Josh Bloch and Doug Lea
 * @since 1.2
 */
public class ThreadLocal<T> {

  /**
   * ThreadLocals rely on per-thread linear-probe hash maps attached
   * to each thread (Thread.threadLocals and
   * inheritableThreadLocals).  The ThreadLocal objects act as keys,
   * searched via threadLocalHashCode.  This is a custom hash code
   * (useful only within ThreadLocalMaps) that eliminates collisions
   * in the common case where consecutively constructed ThreadLocals
   * are used by the same threads, while remaining well-behaved in
   * less common cases.
   */
  private final int threadLocalHashCode = nextHashCode();

  /**
   * The next hash code to be given out. Updated atomically. Starts at
   * zero.
   */
  private static AtomicInteger nextHashCode =
      new AtomicInteger();

  /**
   * The difference between successively generated hash codes - turns
   * implicit sequential thread-local IDs into near-optimally spread
   * multiplicative hash values for power-of-two-sized tables.
   */
  private static final int HASH_INCREMENT = 0x61c88647;

  /**
   * Returns the next hash code.
   */
  private static int nextHashCode() {
    return nextHashCode.getAndAdd(HASH_INCREMENT);
  }

  /**
   * Returns the current thread's "initial value" for this
   * thread-local variable.  This method will be invoked the first
   * time a thread accesses the variable with the {@link #get}
   * method, unless the thread previously invoked the {@link #set}
   * method, in which case the {@code initialValue} method will not
   * be invoked for the thread.  Normally, this method is invoked at
   * most once per thread, but it may be invoked again in case of
   * subsequent invocations of {@link #remove} followed by {@link #get}.
   *
   * <p>This implementation simply returns {@code null}; if the
   * programmer desires thread-local variables to have an initial
   * value other than {@code null}, {@code ThreadLocal} must be
   * subclassed, and this method overridden.  Typically, an
   * anonymous inner class will be used.
   *
   * @return the initial value for this thread-local
   */
  protected T initialValue() {
    return null;
  }

  /**
   * Creates a thread local variable. The initial value of the variable is
   * determined by invoking the {@code get} method on the {@code Supplier}.
   *
   * @param <S> the type of the thread local's value
   * @param supplier the supplier to be used to determine the initial value
   * @return a new thread local variable
   * @throws NullPointerException if the specified supplier is null
   * @since 1.8
   */
  public static <S> ThreadLocal<S> withInitial(Supplier<? extends S> supplier) {
    return new SuppliedThreadLocal<>(supplier);
  }

  /**
   * Creates a thread local variable.
   *
   * @see #withInitial(java.util.function.Supplier)
   */
  public ThreadLocal() {
  }

  /**
   * Returns the value in the current thread's copy of this
   * thread-local variable.  If the variable has no value for the
   * current thread, it is first initialized to the value returned
   * by an invocation of the {@link #initialValue} method.
   *
   * @return the current thread's value of this thread-local
   */
  public T get() {
    // 使用当前线程从线程中获取属性
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
      ThreadLocalMap.Entry e = map.getEntry(this);
      if (e != null) {
        @SuppressWarnings("unchecked")
        T result = (T) e.value;
        return result;
      }
    }
    return setInitialValue();
  }

  /**
   * Variant of set() to establish initialValue. Used instead
   * of set() in case user has overridden the set() method.
   *
   * @return the initial value
   */
  private T setInitialValue() {
    T value = initialValue();
    Thread t = Thread.currentThread();
    ThreadLocalMap map = getMap(t);
    if (map != null) {
      map.set(this, value);
    } else {
      createMap(t, value);
    }
    return value;
  }

  /**
   * Sets the current thread's copy of this thread-local variable
   * to the specified value.  Most subclasses will have no need to
   * override this method, relying solely on the {@link #initialValue}
   * method to set the values of thread-locals.
   *
   * @param value the value to be stored in the current thread's copy of this thread-local.
   */
  public void set(T value) {
    // 获取当前执行的线程， 使用当前线程作为KEY保存
    Thread t = Thread.currentThread();

    // 从 当前线程Thread 中拿到一个Map，然后把value放到这个线程的map中
    // 因为每个线程都有一个自己的Map，也就是 threadLocals，从而起到了线程隔离的作用
    ThreadLocalMap map = getMap(t);

    // 如果map不为空，说明当前线程已经构造过ThreadLocalMap，直接将值存储到map中
    if (map != null) {
      map.set(this, value);
    } else {
      // 如果map为空，说明是第一次使用，调用 createMap构造， 创建(以当前Thread变量为键值，以ThreadLocal要保存的副本变量为value)
      createMap(t, value);
    }
  }

  /**
   * Removes the current thread's value for this thread-local
   * variable.  If this thread-local variable is subsequently
   * {@linkplain #get read} by the current thread, its value will be
   * reinitialized by invoking its {@link #initialValue} method,
   * unless its value is {@linkplain #set set} by the current thread
   * in the interim.  This may result in multiple invocations of the
   * {@code initialValue} method in the current thread.
   *
   * @since 1.5
   */
  public void remove() {
    ThreadLocalMap m = getMap(Thread.currentThread());
    if (m != null) {
      m.remove(this);
    }
  }

  /**
   * Get the map associated with a ThreadLocal. Overridden in
   * InheritableThreadLocal.
   *
   * @param t the current thread
   * @return the map
   */
  ThreadLocalMap getMap(Thread t) {
    return t.threadLocals;
  }

  /**
   * Create the map associated with a ThreadLocal. Overridden in
   * InheritableThreadLocal.
   *
   * @param t the current thread
   * @param firstValue value for the initial entry of the map
   */
  void createMap(Thread t, T firstValue) {
    t.threadLocals = new ThreadLocalMap(this, firstValue);
  }

  /**
   * Factory method to create map of inherited thread locals.
   * Designed to be called only from Thread constructor.
   *
   * @param parentMap the map associated with parent thread
   * @return a map containing the parent's inheritable bindings
   */
  static ThreadLocalMap createInheritedMap(ThreadLocalMap parentMap) {
    return new ThreadLocalMap(parentMap);
  }

  /**
   * Method childValue is visibly defined in subclass
   * InheritableThreadLocal, but is internally defined here for the
   * sake of providing createInheritedMap factory method without
   * needing to subclass the map class in InheritableThreadLocal.
   * This technique is preferable to the alternative of embedding
   * instanceof tests in methods.
   */
  T childValue(T parentValue) {
    throw new UnsupportedOperationException();
  }

  /**
   * An extension of ThreadLocal that obtains its initial value from
   * the specified {@code Supplier}.
   */
  static final class SuppliedThreadLocal<T> extends ThreadLocal<T> {

    private final Supplier<? extends T> supplier;

    SuppliedThreadLocal(Supplier<? extends T> supplier) {
      this.supplier = Objects.requireNonNull(supplier);
    }

    @Override
    protected T initialValue() {
      return supplier.get();
    }
  }

  /**
   * ThreadLocalMap is a customized hash map suitable only for
   * maintaining thread local values. No operations are exported
   * outside of the ThreadLocal class. The class is package private to
   * allow declaration of fields in class Thread.  To help deal with
   * very large and long-lived usages, the hash table entries use
   * WeakReferences for keys. However, since reference queues are not
   * used, stale entries are guaranteed to be removed only when
   * the table starts running out of space.
   */
  static class ThreadLocalMap {

    /**
     * The entries in this hash map extend WeakReference, using
     * its main ref field as the key (which is always a
     * ThreadLocal object).  Note that null keys (i.e. entry.get()
     * == null) mean that the key is no longer referenced, so the
     * entry can be expunged from table.  Such entries are referred to
     * as "stale entries" in the code that follows.
     */
    static class Entry extends WeakReference<ThreadLocal<?>> {

      /**
       * The value associated with this ThreadLocal.
       */
      Object value;

      Entry(ThreadLocal<?> k, Object v) {
        super(k);
        value = v;
      }
    }

    /**
     * The initial capacity -- MUST be a power of two.
     */
    private static final int INITIAL_CAPACITY = 16;

    /**
     * The table, resized as necessary.
     * table.length MUST always be a power of two.
     */
    private Entry[] table;

    /**
     * The number of entries in the table.
     */
    private int size = 0;

    /**
     * The next size value at which to resize.
     */
    private int threshold; // Default to 0

    /**
     * Set the resize threshold to maintain at worst a 2/3 load factor.
     */
    private void setThreshold(int len) {
      threshold = len * 2 / 3;
    }

    /**
     * Increment i modulo len.
     */
    private static int nextIndex(int i, int len) {
      return ((i + 1 < len) ? i + 1 : 0);
    }

    /**
     * Decrement i modulo len.
     */
    private static int prevIndex(int i, int len) {
      return ((i - 1 >= 0) ? i - 1 : len - 1);
    }

    /**
     * Construct a new map initially containing (firstKey, firstValue).
     * ThreadLocalMaps are constructed lazily, so we only create
     * one when we have at least one entry to put in it.
     */
    ThreadLocalMap(ThreadLocal<?> firstKey, Object firstValue) {
      // 构造一个 Entry 数组，并设置初始大小
      table = new Entry[INITIAL_CAPACITY];
      // 计算 Entry 数组下标
      int i = firstKey.threadLocalHashCode & (INITIAL_CAPACITY - 1);
      // 将 firstValue 存储到指定的  table 下标中
      table[i] = new Entry(firstKey, firstValue);
      // 设置节点长度为 1
      size = 1;
      // 设置扩容的阈值
      setThreshold(INITIAL_CAPACITY);
    }

    /**
     * Construct a new map including all Inheritable ThreadLocals
     * from given parent map. Called only by createInheritedMap.
     *
     * @param parentMap the map associated with parent thread.
     */
    private ThreadLocalMap(ThreadLocalMap parentMap) {
      Entry[] parentTable = parentMap.table;
      int len = parentTable.length;
      setThreshold(len);
      table = new Entry[len];

      for (int j = 0; j < len; j++) {
        Entry e = parentTable[j];
        if (e != null) {
          @SuppressWarnings("unchecked")
          ThreadLocal<Object> key = (ThreadLocal<Object>) e.get();
          if (key != null) {
            Object value = key.childValue(e.value);
            Entry c = new Entry(key, value);
            int h = key.threadLocalHashCode & (len - 1);
            while (table[h] != null) {
              h = nextIndex(h, len);
            }
            table[h] = c;
            size++;
          }
        }
      }
    }

    /**
     * Get the entry associated with key.  This method
     * itself handles only the fast path: a direct hit of existing
     * key. It otherwise relays to getEntryAfterMiss.  This is
     * designed to maximize performance for direct hits, in part
     * by making this method readily inlinable.
     *
     * @param key the thread local object
     * @return the entry associated with key, or null if no such
     */
    private Entry getEntry(ThreadLocal<?> key) {
      int i = key.threadLocalHashCode & (table.length - 1);
      Entry e = table[i];
      if (e != null && e.get() == key) {
        return e;
      } else {
        return getEntryAfterMiss(key, i, e);
      }
    }

    /**
     * Version of getEntry method for use when key is not found in
     * its direct hash slot.
     *
     * @param key the thread local object
     * @param i the table index for key's hash code
     * @param e the entry at table[i]
     * @return the entry associated with key, or null if no such
     */
    private Entry getEntryAfterMiss(ThreadLocal<?> key, int i, Entry e) {
      Entry[] tab = table;
      int len = tab.length;

      while (e != null) {
        ThreadLocal<?> k = e.get();
        if (k == key) {
          return e;
        }
        if (k == null) {
          expungeStaleEntry(i);
        } else {
          i = nextIndex(i, len);
        }
        e = tab[i];
      }
      return null;
    }

    /**
     * Set the value associated with key.
     *
     * @param key the thread local object
     * @param value the value to be set
     */
    private void set(ThreadLocal<?> key, Object value) {

      // We don't use a fast path as with get() because it is at
      // least as common to use set() to create new entries as
      // it is to replace existing ones, in which case, a fast
      // path would fail more often than not.

      Entry[] tab = table;
      int len = tab.length;
      // 根据 哈希码 和 数组长度，求元素放置的下标
      int i = key.threadLocalHashCode & (len - 1);

      // 从 1 开始往后一直遍历到 最后一个 Entry， 线性探索
      for (Entry e = tab[i];
          e != null;
          e = tab[i = nextIndex(i, len)]) {
        ThreadLocal<?> k = e.get();

        // 如果 key 相等，覆盖 value
        if (k == key) {
          e.value = value;
          return;
        }

        // 如果 key 为 null, 用新key， 新value覆盖，同时清理历史 key = null 的旧数据
        if (k == null) {
          replaceStaleEntry(key, value, i);
          return;
        }
      }

      tab[i] = new Entry(key, value);
      int sz = ++size;

      // 如果超过阈值，则扩容
      if (!cleanSomeSlots(i, sz) && sz >= threshold) {
        rehash();
      }
    }

    /**
     * Remove the entry for key.
     */
    private void remove(ThreadLocal<?> key) {
      Entry[] tab = table;
      int len = tab.length;
      int i = key.threadLocalHashCode & (len - 1);
      for (Entry e = tab[i];
          e != null;
          e = tab[i = nextIndex(i, len)]) {
        if (e.get() == key) {
          e.clear();
          expungeStaleEntry(i);
          return;
        }
      }
    }

    /**
     *
     * 由于Entry的key为弱引用，如果key为空，说明ThreadLocal这个对象被GC回收了。 replaceStaleEntry的作用就是把陈旧的Entry进行替换
     *
     * Replace a stale entry encountered during a set operation
     * with an entry for the specified key.  The value passed in
     * the value parameter is stored in the entry, whether or not
     * an entry already exists for the specified key.
     *
     * As a side effect, this method expunges all stale entries in the
     * "run" containing the stale entry.  (A run is a sequence of entries
     * between two null slots.)
     *
     * @param key the key
     * @param value the value to be associated with key
     * @param staleSlot index of the first stale entry encountered while searching for key.
     */
    private void replaceStaleEntry(ThreadLocal<?> key, Object value,
        int staleSlot) {
      Entry[] tab = table;
      int len = tab.length;
      Entry e;

      // 向前扫描，查找最前一个无效的  slot
      // Back up to check for prior stale entry in current run.
      // We clean out whole runs at a time to avoid continual
      // incremental rehashing due to garbage collector freeing
      // up refs in bunches (i.e., whenever the collector runs).
      int slotToExpunge = staleSlot;
      for (int i = prevIndex(staleSlot, len);
          (e = tab[i]) != null;
          i = prevIndex(i, len)) {
        if (e.get() == null) {
          // 通过循环遍历，可以定位到最前面一个无效的slot
          slotToExpunge = i;
        }
      }

      // Find either the key or trailing null slot of run, whichever
      // occurs first
      for (int i = nextIndex(staleSlot, len);
          (e = tab[i]) != null;
          i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();

        // If we find key, then we need to swap it
        // with the stale entry to maintain hash table order.
        // The newly stale slot, or any other stale slot
        // encountered above it, can then be sent to expungeStaleEntry
        // to remove or rehash all of the other entries in run.
        if (k == key) {
          e.value = value;

          tab[i] = tab[staleSlot];
          tab[staleSlot] = e;

          // Start expunge at preceding stale entry if it exists
          if (slotToExpunge == staleSlot) {
            slotToExpunge = i;
          }
          cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
          return;
        }

        // If we didn't find stale entry on backward scan, the
        // first stale entry seen while scanning for key is the
        // first still present in the run.
        if (k == null && slotToExpunge == staleSlot) {
          slotToExpunge = i;
        }
      }

      // If key not found, put new entry in stale slot
      tab[staleSlot].value = null;
      tab[staleSlot] = new Entry(key, value);

      // If there are any other stale entries in run, expunge them
      if (slotToExpunge != staleSlot) {
        cleanSomeSlots(expungeStaleEntry(slotToExpunge), len);
      }
    }

    /**
     * Expunge a stale entry by rehashing any possibly colliding entries
     * lying between staleSlot and the next null slot.  This also expunges
     * any other stale entries encountered before the trailing null.  See
     * Knuth, Section 6.4
     *
     * @param staleSlot index of slot known to have null key
     * @return the index of the next null slot after staleSlot (all between staleSlot and this slot
     * will have been checked for expunging).
     */
    private int expungeStaleEntry(int staleSlot) {
      Entry[] tab = table;
      int len = tab.length;

      // expunge entry at staleSlot
      tab[staleSlot].value = null;
      tab[staleSlot] = null;
      size--;

      // Rehash until we encounter null
      Entry e;
      int i;
      for (i = nextIndex(staleSlot, len);
          (e = tab[i]) != null;
          i = nextIndex(i, len)) {
        ThreadLocal<?> k = e.get();
        if (k == null) {
          e.value = null;
          tab[i] = null;
          size--;
        } else {
          int h = k.threadLocalHashCode & (len - 1);
          if (h != i) {
            tab[i] = null;

            // Unlike Knuth 6.4 Algorithm R, we must scan until
            // null because multiple entries could have been stale.
            while (tab[h] != null) {
              h = nextIndex(h, len);
            }
            tab[h] = e;
          }
        }
      }
      return i;
    }

    /**
     * Heuristically scan some cells looking for stale entries.
     * This is invoked when either a new element is added, or
     * another stale one has been expunged. It performs a
     * logarithmic number of scans, as a balance between no
     * scanning (fast but retains garbage) and a number of scans
     * proportional to number of elements, that would find all
     * garbage but would cause some insertions to take O(n) time.
     *
     * @param i a position known NOT to hold a stale entry. The scan starts at the element after i.
     * @param n scan control: {@code log2(n)} cells are scanned, unless a stale entry is found, in
     * which case {@code log2(table.length)-1} additional cells are scanned. When called from
     * insertions, this parameter is the number of elements, but when from replaceStaleEntry, it is
     * the table length. (Note: all this could be changed to be either more or less aggressive by
     * weighting n instead of just using straight log n. But this version is simple, fast, and seems
     * to work well.)
     * @return true if any stale entries have been removed.
     */
    private boolean cleanSomeSlots(int i, int n) {
      boolean removed = false;
      Entry[] tab = table;
      int len = tab.length;
      do {
        i = nextIndex(i, len);
        Entry e = tab[i];
        if (e != null && e.get() == null) {
          n = len;
          removed = true;
          i = expungeStaleEntry(i);
        }
      } while ((n >>>= 1) != 0);
      return removed;
    }

    /**
     * Re-pack and/or re-size the table. First scan the entire
     * table removing stale entries. If this doesn't sufficiently
     * shrink the size of the table, double the table size.
     */
    private void rehash() {
      expungeStaleEntries();

      // Use lower threshold for doubling to avoid hysteresis
      if (size >= threshold - threshold / 4) {
        resize();
      }
    }

    /**
     * Double the capacity of the table.
     */
    private void resize() {
      Entry[] oldTab = table;
      int oldLen = oldTab.length;
      int newLen = oldLen * 2;
      Entry[] newTab = new Entry[newLen];
      int count = 0;

      for (int j = 0; j < oldLen; ++j) {
        Entry e = oldTab[j];
        if (e != null) {
          ThreadLocal<?> k = e.get();
          if (k == null) {
            e.value = null; // Help the GC
          } else {
            int h = k.threadLocalHashCode & (newLen - 1);
            while (newTab[h] != null) {
              h = nextIndex(h, newLen);
            }
            newTab[h] = e;
            count++;
          }
        }
      }

      setThreshold(newLen);
      size = count;
      table = newTab;
    }

    /**
     * Expunge all stale entries in the table.
     */
    private void expungeStaleEntries() {
      Entry[] tab = table;
      int len = tab.length;
      for (int j = 0; j < len; j++) {
        Entry e = tab[j];
        if (e != null && e.get() == null) {
          expungeStaleEntry(j);
        }
      }
    }
  }
}
